/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年10月19日
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/

#include <iostream>
#include <vector>

using namespace std;

class Solution{
public:
    int minFallingPathSum(vector<vector<int>> &A){
        int len = A.size();
        int tmpmin;
        for(int i = 1; i < len; i++){
            for(int j = 0; j < len; j++){
                tmpmin = A[i-1][j];
                if( j > 0 ){
                    tmpmin = min(tmpmin, A[i-1][j-1]);
                }

                if(j + 1 < len){
                    tmpmin = min(tmpmin, A[i-1][j+1]);
                }

                A[i][j] += tmpmin;
            }
        }

        tmpmin = A[len-1][0];
        for(int i = 1; i < len; i++){
            tmpmin = min(tmpmin, A[len-1][i]);
        }

        return tmpmin;
    }
};